package cn.dlc.com.heap;

import lombok.Data;

import java.lang.reflect.Array;
import java.util.Comparator;

/**
 * @author 邓立川
 * @date 2021/3/25 20:35
 * @desc 当前类的描述信息
 */

@Data
public class Heap<T extends Comparable<T>> {

    private T[] items;
    private int num;

    public Heap(int capacity){
        // 初始化数据的长度，而不是元素的个数
        this.items = (T[])new Comparable[capacity + 1];
        this.num = 0;
    }

    // 比较值的大小
    public boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    // 交换两个值
    public void exchange(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    // 添加元素
    public void insert(T t) {
        // 可以看到第一个位置没有添加元素
        items[++num] = t;
        // 让这个元素上浮
        swim(num);
    }

    // 让k元素上浮
    private void swim(int k) {
        // 结束条件是比较到根节点。因为根节点的索引是1
        while(k > 1) {
            // 我们默认第一个节点不放元素，这样更好计算
            if(less(k / 2, k)) {
                // 父节点的元素更小,交换元素
                exchange(k / 2, k);
            } else {
                // 父节点的元素大，那么不需要比较了，
                break;
            }
            // 重新设置值
            k = k / 2;
        }
    }

    // 删除最大元素
    public T delMax(){
        T t = items[1];
        // 1、交换1和最大位置处的元素
        exchange(1, num);
        // 2、删除最大位置的元素（就是删除原来索引为1处的元素）
        items[num] = null;
        num--;
        // 3、下浮1处位置的元素
        sink(1);
        return t;
    }

    // 下沉方法。
    private void sink(int k) {
        // num > 2*k表示当前节点还有子节点
        // 如果小于的话，就没有子节点了，
        while(num >= 2*k) {

            // 用来接收子节点中更大值的索引
            int max;

            // 如果还有右子结点
            if(num >= 2*k + 1) {
                if(less(2*k, 2*k+1)) {
                    // 左子节点更小，那么max为右子结点
                    max = 2*k + 1;
                } else {
                    max = 2*k;
                }
            } else {
                // 没有右子结点了
                max = 2*k;
            }

            // 比较当前节点和右子结点
            if(less(max, k)) {
                // 子节点更小，那么不需要比较了
                break;
            } else {
                // 否则交换位置，
                exchange(max, k);
                // 并且继续比较
                k = max;
            }
        }
    }



}
